#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/9/1 8:50
# ===========================================
#       题目名称： 51. N 皇后
#       题目地址： https://leetcode.cn/problems/n-queens/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import List


class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if not 1 <= n <= 9:
            return []
        dps = []  # 皇后群
        i = 0  # 第几个皇后
        while i < n:
            if i == 0:
                for j in range(n):
                    dp = [["."] * n for _ in range(n)]  # 定义好初始化的N皇后
                    dp[i][j] = "Q"
                    dps.append(dp)
            else:
                temp_dps = []
                for dp in dps:  # 遍历每个棋盘, 找到当前这个符合条件的坐标
                    for j in range(n):  # 找到当前符合条件的坐标
                        is_ok = True  # 判断是否符合规范
                        # x 因为是遍历所以不需要判断
                        # y 判断是否存在同一列出现
                        cur_index = 0
                        while is_ok and cur_index < n:
                            if dp[cur_index][j] == "Q":
                                is_ok = False
                                break
                            cur_index += 1
                        if not is_ok:
                            continue
                            # 斜线判断 i, j
                        """
                            00  01  02  03
                            10  11  12  13
                            20  21  22  23
                            30  31  32  33
                            如果 为11
                        """
                        # 左上角
                        x, y = i - 1, j - 1
                        while is_ok and x > -1 and y > -1:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x -= 1
                            y -= 1
                        # 右上角
                        x, y = i - 1, j + 1
                        while is_ok and x > -1 and y < n:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x -= 1
                            y += 1
                            # 左下角
                        x, y = i + 1, j - 1
                        while is_ok and x < n and y > -1:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x += 1
                            y -= 1
                        # 右下角
                        x, y = i + 1, j + 1
                        while is_ok and x < n and y < n:
                            if dp[x][y] == "Q":
                                is_ok = False
                                break
                            x += 1
                            y += 1
                        if is_ok:
                            # 将符合规范的数据存入临时列表
                            cur_dp = [item.copy() for item in dp].copy()
                            cur_dp[i][j] = "Q"
                            temp_dps.append(cur_dp)
                dps = temp_dps
            # 移动一下位置
            i += 1
        return [["".join(item) for item in dp] for dp in dps]

    def solveNQueens2(self, n: int) -> List[List[str]]:
        if not 1 <= n <= 9:
            return []
        dps = []  # 皇后群
        i = 0  # 第几个皇后
        while i < n:
            if i == 0:
                for j in range(n):
                    dp = [["."] * n for _ in range(n)]  # 定义好初始化的N皇后
                    dp[i][j] = "Q"
                    dps.append(dp)
            else:
                temp_dps = []
                for dp in dps:  # 遍历每个棋盘, 找到当前这个符合条件的坐标
                    temp_dp = ["".join(item) for item in dp]
                    cur_dp = [".Q...", "...Q.", "Q....", "....Q", "....."]
                    if i == 4 and cur_dp == temp_dp:
                        print("----")
                    for j in range(n):  # 找到当前符合条件的坐标
                        is_ok = True  # 判断是否符合规范
                        # x 因为是遍历所以不需要判断
                        # y 判断是否存在同一列出现
                        cur_index = 0
                        while is_ok and cur_index < n:
                            if dp[cur_index][j] == "Q":
                                is_ok = False
                                break
                            cur_index += 1
                        if not is_ok:
                            continue
                            # 斜线判断 i, j
                        """
                            00  01  02  03
                            10  11  12  13
                            20  21  22  23
                            30  31  32  33
                            如果 为11
                        """
                        # 左上角
                        if i - 1 > -1 and j - 1 > -1:
                            if dp[i - 1][j - 1] == "Q":
                                continue
                        # 右上角
                        if i - 1 > -1 and j + 1 < n:
                            if dp[i - 1][j + 1] == "Q":
                                continue
                        # 左下角
                        if i + 1 < n and j - 1 > -1:
                            if dp[i + 1][j - 1] == "Q":
                                continue
                        # 右下角
                        if i + 1 < n and j + 1 < n:
                            if dp[i + 1][j + 1] == "Q":
                                continue
                        # 将符合规范的数据存入临时列表
                        cur_dp = [item.copy() for item in dp].copy()
                        cur_dp[i][j] = "Q"
                        temp_dps.append(cur_dp)
                dps = temp_dps
            # 移动一下位置
            i += 1
        return [["".join(item) for item in dp] for dp in dps]


if __name__ == '__main__':
    s = Solution()
    # [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    print([[".Q..", "...Q", "Q...", "..Q."], ["..Q.", "Q...", "...Q", ".Q.."]] == s.solveNQueens(n=4))
    # [["Q"]]
    print([["Q"]] == s.solveNQueens(n=1))
    res5 = [["Q....", "..Q..", "....Q", ".Q...", "...Q."], ["Q....", "...Q.", ".Q...", "....Q", "..Q.."], [".Q...", "...Q.", "Q....", "..Q..", "....Q"], [".Q...", "....Q", "..Q..", "Q....", "...Q."], ["..Q..", "Q....", "...Q.", ".Q...", "....Q"], ["..Q..", "....Q", ".Q...", "...Q.", "Q...."], ["...Q.", "Q....", "..Q..", "....Q", ".Q..."], ["...Q.", ".Q...", "....Q", "..Q..", "Q...."], ["....Q", ".Q...", "...Q.", "Q....", "..Q.."], ["....Q", "..Q..", "Q....", "...Q.", ".Q..."]]
    print(res5 == s.solveNQueens(n=5))
